#include<iostream>
#include <algorithm>

using namespace std;

// 检查该数字是否超过一半
bool checkMoreThanHalf(int * data, int length, int result){
	bool isMoreThanHalf = false;
	// 标志输入是否有效
	bool isVaild = true;
	int count = 0;
	for ( int i = 0; i < length; i++ ){
		if ( data[i] == result ){
			count++;
		}
	}
	if ( count * 2 <= length ){
		isVaild = false;
	}else {
		isMoreThanHalf = true;
	}
	return isMoreThanHalf;
}

int MoreThanHalfNum(int * data, int length){
	// 找超过出现一半的数字
	if ( data == nullptr || length <= 0 )
		return -1;
	int result = data[0];
	int time = 1;
	for ( int i = 0; i<length; i++){
		if ( time == 0 ){
			result = data[i];
		}else if ( result == data[i] ){
			time ++;
		}else {
			time --;
		}
	}
	if ( checkMoreThanHalf(data, length, result)){
		return result;
	}else {
		return -1;
	}
}

int getMiddleIndex(int *data, int start, int end){
	int middle = ( (end- start) >> 1 ) + start;
	// 有序
	if ( data[start] > data[end] ){
		if ( data[middle] > data[start] ){
			return start;
		}else if ( data[middle] < data[end] ){
			return end;
		}else {
			return middle;
		}
	}else{
		if ( data[middle] < data[start] ){
			return start;
		}else if ( data[middle] > data[end] ){
			return end;
		}else {
			return middle;
		}
	}
}


int getSentryIndex(int * data, int low, int high){
	int middle = getMiddleIndex(data, low, high);
	swap(data[middle], data[high]);
	int start = low;
	int end = high - 1;
	while ( start < end ){
		while ( start < end && data[start] <= data[high] ){
			start ++;		
		}

		while ( start < end && data[end] > data[high] ){
			end --;
		}
		swap(data[start], data[end]);
	}
	swap(data[start], data[high]);
	return start;
}

void print(int *data, int length){
	for (int i=0;i<length;i++){
		cout << data[i] << "  ";
	}
    cout << endl;
}

void quickSort(int * data, int start, int end){
	if ( start >= end )
		return;
	int middle = getSentryIndex(data, start, end);
	quickSort(data, start, middle-1);
	quickSort(data, middle+1, end);	
}

// 使用快速排序
int getMoreThanHalfNum(int * data, int length){
	if ( data == nullptr || length <= 0 )
		return -1;
	quickSort(data, 0, length-1);
	int middle = length >> 1;
	if ( checkMoreThanHalf(data, length, data[middle]) ){
		return data[middle];
	}else {
		return -1;
	}
}

int main(void){

    int numbers[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
    int result = getMoreThanHalfNum(numbers, sizeof(numbers)/sizeof(int));
    cout << result << endl;
    
    int numbers1[] = {1, 2, 3, 2, 4, 2, 5, 2, 3};
    result = getMoreThanHalfNum(numbers1, sizeof(numbers1)/sizeof(int));
    cout << result << endl;
    int numbers2[] = {2, 2, 2, 2, 2, 1, 3, 4, 5};
    result = getMoreThanHalfNum(numbers2, sizeof(numbers2)/sizeof(int));
    cout << result << endl;
    int numbers3[] = {1, 3, 4, 5, 2, 2, 2, 2, 2};
    result = getMoreThanHalfNum(numbers3, sizeof(numbers3)/sizeof(int));
    cout << result << endl;
    int numbers4[] = {1};
    result = getMoreThanHalfNum(numbers4, sizeof(numbers4)/sizeof(int));
    cout << result << endl;
  
    result = getMoreThanHalfNum(nullptr,0);
    cout << result << endl;

    return 0;
}